Given the continually increased reliance on computers in contemporary society, computer technology has had to advance on many fronts to keep up with increased demand. One particular subject of significant research and development efforts is parallelism, i.e., the performance of multiple tasks in parallel.
A number of computer software and hardware technologies have been developed to facilitate increased parallel processing. From a hardware standpoint, computers increasingly rely on multiple microprocessors to provide increased workload capacity. Furthermore, some microprocessors have been developed that support the ability to execute multiple threads in parallel, effectively providing many of the same performance gains attainable through the use of multiple microprocessors. From a software standpoint, multithreaded operating systems and kernels have been developed, which permit computer programs to concurrently execute in multiple threads so that multiple tasks can essentially be performed at the same time.
In addition, some computers implement the concept of logical partitioning, where a single physical computer is permitted to operate essentially like multiple and independent “virtual” computers (referred to as logical partitions), with the various resources in the physical computer (e.g., processors, memory, input/output devices) allocated among the various logical partitions. Each logical partition executes a separate operating system, and from the perspective of users and of the software applications executing on the logical partition, operates as a fully independent computer.
While parallelism effectively increases system performance by virtue of the ability to perform multiple tasks at once, one side effect of parallelism is increased system complexity due to the need to synchronize the operation of multiple concurrent processes or threads, particularly with regard to data structures and other system resources that are capable of being accessed by multiple processes or threads. Separate processes or threads that are capable of accessing specific shared data structures are typically not aware of the activities of other threads or processes. As such, a risk exists that one thread might access a specific data structure in an unexpected manner relative to another thread, creating indeterminate results and potential system errors.
As an example, the possibility exists that one thread may retrieve data from a data structure, while another thread may later change the data structure in some manner, resulting in each thread seeing a different state for the data structure. Efforts must be made, however, to ensure that the state of a data structure be consistent when viewed by different threads, otherwise indeterminate results can occur.
As but one of many examples, some computer systems concerned with resiliency and high availability rely on journaling systems to log changes to data structures such as objects and permit such objects to be recovered in the event of a failure in the computer system. As objects change, journal entries are typically created and written to a non-volatile memory such as a disk drive so that the objects can be recreated in the computer system's main (volatile) memory after a failure.
Some journaling systems are remote in nature, whereby activities that occur on one computer are duplicated on a second, redundant computer. In these remote journaling applications, the journaling systems on the redundant computers are often able to switch between live and standby modes. In a live mode, journal entries received from the primary computer are written directly to non-volatile storage on the redundant computer, along with maintaining current copies of the objects in the redundant computer's volatile memory by applying the journal entries to the copies of the objects in volatile memory. In a standby mode, the copies of the objects in the redundant computer are still kept current; however, the journal entries received from the primary computer are not written to non-volatile storage by the redundant computer.
It has been found that, when switching from standby mode to live mode, objects in volatile memory need to be forced or written to non-volatile storage so that later journal entries work off of the non-volatile copy of the objects for updates. However, for performance reasons, it is often desirable to allow a journal to switch modes prior to forcing all objects to non-volatile storage, and thereafter allow objects to be forced to non-volatile storage in connection with changes made to those objects. Consistency requires that an object be forced to non-volatile storage before a change is made to that object. As a result, any object that is being changed typically must be queried to determine whether the object needs to be forced to non-volatile storage prior to making the change.
Given, however, that objects may be concurrently accessed by different processes, a concern exists that a process attempting to query an object prior to modifying that object may do so at the same time the object is being modified by another process, which could potentially lead to indeterminate results, and potential system errors.
To address these concerns, a serialization mechanism such as a lock or semaphore may be used to limit the access to a shared data structure or other shared resource to one process at a time. A lock or semaphore is essentially a “token” that can be obtained exclusively by a process or thread in a multithreaded environment to access a particular shared resource. Before a process or thread can access a resource, it must first obtain the token from the system. If another process or thread currently possesses the token, the former process or thread is not permitted to access the resource until the token is released by the other process or thread. In this manner, the accesses to the resource are effectively “serialized” to prevent indeterminate operations from occurring.
In some environments, different types of locks or semaphores may be used. For example, “exclusive” locks or semaphores may be used to gate write access to a shared resource such as a data structure, so that only one thread is permitted to access a data structure when the state of the data structure is being modified. “Shared” locks or semaphores, however, may be used to gate read access to a data structure, to permit multiple threads that are not intending to modify the state of the data structure to concurrently access the data structure to obtain its current state.
While locks and semaphores enable a programmer to ensure complete serialization of a data structure or other shared resource, it has been found that the operations associated with obtaining such locks and semaphores can add significant overhead, and as a result, have an adverse impact on system performance, particularly in applications where data structures are frequently read but rarely modified.
For example, in the aforementioned journaling application, it may be desirable to use a semaphore in connection with querying journaled objects when transitioning from standby to live mode. Obtaining a semaphore, however, can add significant additional processing to the code path for querying journaled objects, and thus substantially increase the performance overhead of such an operation. Given the relative infrequency of updates to journaled objects as a whole, and the substantial overhead associated with querying large numbers of journaled objects, much of the effort associated with obtaining semaphores is effectively wasteful and burdensome on system performance.
A substantial need therefore exists in the art for a manner of maintaining consistency of a data structure or other shared resource among multiple threads in a multithreaded environment with lower overhead than typically provided by conventional serialization mechanisms.